Міністерство освіти і науки України Чернівецький національний університет ім. Ю. Федьковича Математичний факультет Кафедра математичних проблем управління і кібернетики МАРШРУТИЗАЦІЯ В МЕРЕЖАХ ПЕРЕДАЧІ ДАНИХ курсова робота Науковий керівник: Ассистент кафедри МПУіК Коцур М.П. Чернівці 2002 Зміст Вступ 3 1. Основні поняття, що використовуються при маршрутизації в мережах 3 2. Використання графів в мережевих алгоритмах 6 2.1. Основні поняття теорії графів 6 2.2. Постановка задачі вибору найкоротшого шляху 7 2.3. Способи представлення графів у пам'яті ЕОМ. 8 2.3.1. Вимоги до представлення графів 9 2.3.2. Матриця суміжності 9 2.3.3. Матриця інциденцій 10 2.3.4. Списки суміжності 10 2.3.5. Масив дуг 11 3. Алгоритми пошуку найкоротшого шляху 12 3.1. Алгоритм Беллмана-Форда 12 3.2. Алгоритм Дейкстра 14 3.3. Алгоритм Флойда-Уоршалла 17 4. Сучасні протоколи маршрутизації на основі алгоритма Беллмана-Форда 18 4.1. Протокол RIP 18 4.2. Протокол маршрутизації OSPF 20 5. Опис програми 21 6. Контрольні приклади 22 Висновки 23 Література 24 Вступ Під алгоритмом маршрутизації ми часто розуміємо протокол мережевого рівня, котрий керує пакетами при їхньому русі по мережі зв'язку до потрібного місця призначення. Моменти часу, коли приймаються рішення про вибір маршруту, залежать від того, використовує мережа дейтаграмну передачу чи віртуальні з'єднання. У дейтаграмній мережі два послідовних пакети однієї і тієї ж пари користувачів можуть проходити по різних маршрутах і вибирати маршрут необхідно індивідуально для кожного пакета. У мережі з віртуальними з'єднаннями маршрут вибирається при встановленні кожного віртуального з'єднання. Всі пакети віртуального з'єднання послідовно використовують цей шлях впритул до моменту, коли або дане віртуальне з'єднання закінчує своє існування, або коли для даного з'єднання по яким-небудь причинам вибирається інший маршрут. Звичайно для вибору маршруту використовується достатньо складний набір алгоритмів, які працюють більш менш незалежно, хоча і обмінюються інформацією. Його складність обумовлена рядом причин. По-перше, маршрутизація потребує координації роботи усіх вузлів підмережі, а не тільки однієї пари модулів. По-друге, система маршрутизації повинна справлятися із виходами з ладу ліній чи вузлів шляхом перенаправлення графіка і обновлення баз даних, що використовуються системою. По-третє, для досягнення найкращих характеристик алгоритм маршрутизації може змінити маршрути у випадку коли деякі області мережі стають перевантаженими. В курсовій роботі розглядаються алгоритми вибору найкоротшого шляху в мережі. Розділ 1 містить опис основних понять, що використовуються при маршрутизації в мережах, а також класифікацію методів маршрутизації. У розділі 2 є інформація про використання графів у мережевих алгоритмах, постановка задачі вибору найкоротшого шляху і способи представлення графів у пам'яті ЕОМ. Розділ 3 містить опис алгоритмів Беллмана-Форда, Дейкстра і Флойда-Уоршалла. Розділ 4 присвячений опису сучасних протоколів маршрутизації в мережі RIP і OSPF. У 5 розділі дається опис програми пошуку найкоротшого шляху в мережі, в розділі 6 – контрольний приклад. 1. Основні поняття, що використовуються при маршрутизації в мережах Двома головними функціями, які виконує алгоритм маршрутизації, є вибір маршрутів для різноманітних пар відправник - адресат і забезпечення правильної доставки повідомлень їх адресатам після того, як вибрані маршрути. Друга функція забезпечується шляхом використання різних протоколів і структур даних, що називаються маршрутними таблицями. Основна увага буде приділена першій функції (вибору маршрутів) і тому, як це впливає на характеристики мережі. Існують дві основні характеристики, на які вагомий вплив здійснює алгоритм маршрутизації - пропускна здатність (кіль...